package interview;

import java.util.HashSet;

public class interview_17_13 {
    public int respace(String[] dictionary, String sentence) {
        HashSet<String> set = new HashSet<>();
        for(int i=0;i< dictionary.length;++i){
            set.add(dictionary[i]);
        }
        int len=sentence.length();
        if(len==0) return 0;
        int[] dp=new int[len];
        for(int i=0;i<len;++i){
            dp[i]=len;
        }
        String tmp=sentence.substring(0,1);
        if(set.contains(tmp)){
            dp[0]=0;
        }else dp[0]=1;
        for(int i=1;i<len;++i){
            for(int j=0;j<i;++j){
                tmp=sentence.substring(j+1,i+1);
                if(set.contains(tmp)){
                    dp[i]=Math.min(dp[i],dp[j]);
                }else{
                    dp[i]=Math.min(dp[i],dp[j]+i-j);
                }
            }
            tmp=sentence.substring(0,i+1);
            if(set.contains(tmp)){
                dp[i]=0;
            }
        }
        return dp[len-1];
    }
}
